/*
 * @Author: szx
 * @Date: 2022-02-28 14:07:49
 * @LastEditTime: 2022-02-28 15:04:17
 * @Description:
 * @FilePath: \leetcode\1400-1499\1477\1477.js
 */
/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var minSumOfLengths = function (arr, target) {
    let sum = 0;
    // 存入数组[长度，开始下标]
    const memo = [];
    let j = 0;

    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];
        while (sum >= target) {
            if (sum == target) memo.push([i - j + 1, j]);
            sum -= arr[j++];
        }
    }
    let min = Infinity;
    memo.sort((a, b) => a[0] - b[0]);
    console.log(memo);
    for (let i = 0; i < memo.length - 1; i++) {
        for (let j = i + 1; j < memo.length; j++) {
            // 两个互不重叠的
            if (memo[i][1] < memo[j][1] && memo[i][1] + memo[i][0] > memo[j][1]) continue;
            if (memo[j][1] < memo[i][1] && memo[j][1] + memo[j][0] > memo[i][1]) continue;

            min = Math.min(min, memo[i][0] + memo[j][0]);
            break;
        }
    }
    return min === Infinity ? -1 : min;
};

var minSumOfLengths = function (arr, target) {
    const n = arr.length;
    // d[i]表示到编号i（不包含i）的情况下满足target目标的最短子数组的长度
    const dp = new Array(n + 1).fill(Infinity);
    let res = Infinity;
    let j = 0,
        sum = 0;
    for (let i = 1; i <= n; i++) {
        sum += arr[i - 1];
        while (sum > target) sum -= arr[j++];
        if (sum === target) {
            const len = i - j;
            dp[i] = Math.min(len, dp[i - 1]);
            res = Math.min(res, dp[j] + len);
        } else {
            dp[i] = dp[i - 1];
        }
    }
    return res === Infinity ? -1 : res;
};
// console.log(minSumOfLengths([3, 2, 2, 4, 3], 3));
// console.log(minSumOfLengths([7, 3, 4, 7], 7));
// console.log(minSumOfLengths([4, 3, 2, 6, 2, 3, 4], 6));
// console.log(minSumOfLengths([5, 5, 4, 4, 5], 3));
console.log(minSumOfLengths([3, 1, 1, 1, 5, 1, 2, 1], 3));
